"""
给定一个二叉树，检查它是否是镜像对称的
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3
进阶：
你可以运用递归和迭代两种方法解决这个问题"""

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    # 递归实现二叉树
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True

        return self.check(root.left, root.right)
    def check(self, left:TreeNode, right:TreeNode):
        if left == None and right == None:
            return True
        elif left == None and right != None:
            return False
        elif left != None and right == None:
            return False
        elif left.val != right.val:
            return False
        return self.check(left.left, right.right) and self.check(left.right, right.left)
    

# 迭代实现二叉树
    def check(self,left:TreeNode, right:TreeNode):
        queue = []
        queue.append(left)
        queue.append(right)

        while queue:
            left = queue.pop(0)
            right = queue.pop(0)
            if left == None and left == None:
                continue
            if ((left == None or right == None)  or (left.val != right.val)):
                return False
            queue.append(left.left)
            queue.append(right.right)

            queue.append(left.right)
            queue.append(right.left)

        return True


